Talk:Kirby-Paris hydra
Games, that make Googology Wiki more fun. Jiawhein \(a\)\(l\) 12:46, April 10, 2013 (UTC) :Jiawhein, I not very like games, I'm mainly the strict googologist and numberist. Ikosarakt1 (talk ^ 18:53, April 10, 2013 (UTC) ::But games are fun! Check applet I linked below, try to get path tree of size 5 (hit Start several times) and look how hard it is to reduce it! LittlePeng9 (talk) 18:57, April 10, 2013 (UTC) ::GAMES FB100Z • talk • 19:13, April 10, 2013 (UTC) ::Wow, that's look really interesting. I will try it. Thanks. Ikosarakt1 (talk ^ 19:12, April 10, 2013 (UTC) ::Little Peng, I just tried this with size 5, and reduced it to 1 after merely 15 steps (without any strategy, just by haphazard clicks). Ikosarakt1 (talk ^ 19:15, April 10, 2013 (UTC) :::It appears the game appends a random number of copies each step, rather than using the step size. Deedlit11 (talk) 19:22, April 10, 2013 (UTC) :::Game uses step size, I can confirm it. I asked you to reduce PATH tree of size 5. It's impossible to reduce it in 15 steps. LittlePeng9 (talk) 19:29, April 10, 2013 (UTC) :::Sorry, yes, I see that. After 120 steps this tree has the size 14790 and lines to the root are merged into the one dark row. Ikosarakt1 (talk ^ 19:39, April 10, 2013 (UTC) :We need a live simulation :D I'd be fine with programming it. FB100Z • talk • 18:43, April 10, 2013 (UTC) ::I'd be fine with finding it on the internet. I actually already did that. Look here. Also, here is written something about it. LittlePeng9 (talk) 18:51, April 10, 2013 (UTC) I'll see if I can do an animation on this. I can verify that the hydra starting with (((()))) takes 37 steps. FB100Z • talk • 19:25, April 10, 2013 (UTC) Wait, but on the picture shown the tree with initial path 4, not 3. (((()))) has path 4, if I understand it correctly. Ikosarakt1 (talk ^ 17:41, April 13, 2013 (UTC) :Size of hydra is 4, but its length (number of edges, diameter of graph or whatever) is 3. :Also, thing you claimed to not be computation of Hydra(3), is computation of Hydra(3). In definition it's said about deleting rightmost leaf, which gives unique strategy. LittlePeng9 (talk) 17:50, April 13, 2013 (UTC) ::Does the rightmost-leaf strategy always produce the longest game? FB100Z • talk • 17:55, April 13, 2013 (UTC) :::Assuming the tree is in "Cantor normal form", i.e. you inductively order the children from largest to smallest, then yes. Shortest game is if you select leaf by taking the greatest child, then greatest child of that child, etc. Deedlit11 (talk) 18:00, April 13, 2013 (UTC) :::Most of times we just take tree, find rightmost leaf, delete it and copy subtree without modifying order in any way. It rarely gives shortest or longest game. LittlePeng9 (talk) 18:45, April 13, 2013 (UTC) :::Consider a hydra starting with a path of length \(n\). Let \(\text{AllHydra}(n)\) be set of all times \(t\) such that Hercules can kill the hydra in exactly \(t\) steps. Is \(\text{AllHydra}(n)\) a continuous range from the shortest game to the largest game? Or does it have gaps? FB100Z • talk • 18:06, April 13, 2013 (UTC) ::::An interesting question! I would think it would be a continuous range, but I don't know for sure. Deedlit11 (talk) 18:20, April 13, 2013 (UTC) :::::I ran a random simulation and I'm convinced that \(\text{AllHydra}(3) = \{21, 22, \ldots, 36, 37\}\). FB100Z • talk • 21:33, April 13, 2013 (UTC) :::::Define \(\text{minHydra}(n)\) as the minimum number of steps needed to kill the hydra. I conjecture, then, that \(\text{AllHydra}(n) = \text{Hydra}(n)\). FB100Z • talk • 21:36, April 13, 2013 (UTC) ::::::Hmm, I get that \(\text{minHydra}(3) = 20\). After two chops you get three 2-paths, then cutting the three 2-paths get you 4 + 5 + 6 root leaves. 3+2+4+5+6 = 20. ::::::Just for the fun of it, I calculated \(\text{minHydra}(4) = 2.655865986803665*10^{13596}\). I proved that \(2^{2^{\text{minHydra}(n)}} < \text{minHydra}(n+1) < \text{minHydra}(n)^{2^{\text{minHydra}(n)}}\), so \(\text{minHydra}(5) \approx 10^{10^{10^{13596}}}, \text{minHydra}(6) \approx 10^{10^{10^{10^{10^{13596}}}}}\), etc. Deedlit11 (talk) 00:29, April 17, 2013 (UTC) :::::::huh. FB100Z • talk • 01:09, April 17, 2013 (UTC) ::::::To be honest, I thought that even existence of winning strategy is independent of PA in general case. With your bound, it seems this belief was wrong. If you're right, MinHydra(n) grows merely below \(f_5(n)\), as it has approximately tetrational growth. This is well under PA provability bound. LittlePeng9 (talk) 05:28, April 17, 2013 (UTC) ::::::\(f_5(n)\) hasn't tetrational growth rate. \(f_0(n)\) is zeration, \(f_1(n)\) is doubling, \(f_2(n)\) is roughly on par with exponentiation, and \(f_3(n)\) with tetration. Ikosarakt1 (talk ^ 09:55, April 17, 2013 (UTC) :::::::Sorry, I meant \(f_4\). This function grows faster than \(f_3\) but much slower than \(f_4\). LittlePeng9 (talk) 12:20, April 17, 2013 (UTC) :::::::In that case, growth rate should be between tetrational and pentational. Ikosarakt1 (talk ^ 12:23, April 17, 2013 (UTC) :::::::Deedlit's lower bound gives MinHydra(n)>2^^(2n), while f_3 grows around 2^^n, so MinHydra grows faster. You can prove that upper bound grows about 2^^(2^n) by looking at how many 2's are in following iterations. So it outgrows f_3, but not significantly. LittlePeng9 (talk) 12:53, April 17, 2013 (UTC) :::::::Growth rates of these functions remains uncalled. Since I'm a googologist, and I like to give names to functions and numbers, I can call \(2 \uparrow\uparrow (2n)\) "doubleto-tetrational growth" and \(2 \uparrow\uparrow (2^n)\) "exponento-tetrational growth", then MinHydra(n) is something between that. Ikosarakt1 (talk ^ ) 13:46, April 17, 2013 (UTC) I found 2 upper bounds for Hydra(4): E100###100 (throogol) and Hydra(5). King2218 (talk) 15:06, May 1, 2014 (UTC) :Do you have a proof for the first one? you're.so. 15:22, May 1, 2014 (UTC) ::I can't put it here. A blog post, maybe? (dunno) King2218 (talk) 15:43, May 1, 2014 (UTC) ::Oh, and it's not that typical kind of proof; it's just some reasoning - I typed ((((())))) in notepad and began reducing it to the form (#()). After that, I did A LOT of overestimation so no blog post probably. (btw is 'overestimation' the right word?) King2218 (talk) 15:54, May 1, 2014 (UTC) :::I'm really curious about that bound, because there hasn't been any found so far. I can't really see what kind of reasoning you could have used for it, as it has constantly increasing variable to it (number of steps). LittlePeng9 (talk) 17:40, May 1, 2014 (UTC) ::::First, I found out that (()) (note that this is directly inside the root) behaves like f1 in FGH. Then, (()()) behaves like f2 and so on. After that, since 10^n grows faster than f1 ... (You probably know where this is going so I'm not gonna explain the whole bit here) King2218 (talk) 07:07, May 2, 2014 (UTC) :::::I understand your idea, but there is a mistake: (()) always reduces to (), no matter what step it is. What do you mean by "inside the root"? LittlePeng9 (talk) 07:41, May 2, 2014 (UTC) Also, it must end in a 9. King2218 (talk) 10:59, May 2, 2014 (UTC) :Can you prove that? Wythagoras (talk) 11:10, May 2, 2014 (UTC) ::I won't believe you on this one without formal proof, King. LittlePeng9 (talk) 11:19, May 2, 2014 (UTC) :::Nah. Just kidding :P King2218 (talk) 11:35, May 2, 2014 (UTC) Infinite variant? What is the point of that section? Imo it should be deleted, but I leave that for discussion. LittlePeng9 (talk) 19:34, May 24, 2015 (UTC) :removed -- ve 19:38, May 24, 2015 (UTC)